# 链表的基本单位--结点
class Node(object):
    def __init__(self, data):
        self.data = data  # 结点的元素值
        self.next = None  # 表示下一个结点的链接


# 链表
class LinkedList(object):
    # 初始化链表
    def __init__(self, head=None):
        self.head = head  # 链表的头结点

    # 添加新结点
    def append(self, new_element):
        """在链表的尾部追加新的元素"""
        # 首先把头结点设为当前结点
        current = self.head
        # 如果头结点存在
        if self.head:
            # 如果头结点有链接
            while current.next:
                # 把链接的结点设置为当前结点, 继续循环
                # 直到当前结点为链表的最后一个结点
                current = current.next
            # 头结点没有链接, 新元素作为头结点的链接
            current.next = new_element
        # 如果头结点不存在
        else:
            # 把新结点设置为头结点
            self.head = new_element

    # 判断链表是否为空链表
    def is_empty(self):
        return not self.head

    # 获取链表长度
    def get_length(self):
        temp = self.head
        length = 0
        # 循环到尾部结点,next=None
        while temp is not None:
            length = length + 1
            temp = temp.next
        return length

    # 插入结点
    def insert(self, position, new_element):
        """在链表的指定索引处插入元素"""
        # 判断下标是否越界
        if position < 0 or position > self.get_length():
            raise IndexError("插入操作超出索引范围")
        temp = self.head
        # 在头结点处插入
        if position == 0:
            new_element.next = temp
            self.head = new_element
            return
        # 找到指定position处插入
        i = 0
        while i < position:
            pre = temp
            temp = temp.next
            i += 1
        pre.next = new_element
        new_element.next = temp

    # 删除结点
    def remove(self, position):
        """从任意位置删除一个元素"""
        # 判断下标是否越界
        if position < 0 or position > self.get_length() - 1:
            raise IndexError("删除操作超出索引范围")
        # 判断是不是空链表
        i = 0
        temp = self.head
        while temp is not None:
            # 删除头结点
            if position == 0:
                # 新的头结点=旧的头结点的next结点
                self.head = temp.next
                # 旧的头结点指向None, 没有前驱也没有后继, 相当于踢出链表
                temp.next = None

            pre = temp
            # 遍历链表
            temp = temp.next
            i += 1
            if i == position:
                # temp的前一个结点直接指向temp的后一个结点
                pre.next = temp.next
                # temp也不再指向后一个结点, 而指向None
                temp.next = None
                return

    # 打印链表
    def print_list(self):
        print('Linked List:')
        temp = self.head
        while temp is not None:
            print(temp.data)
            temp = temp.next

    # 倒置链表
    def reverse(self):
        """将链表反转过来"""
        prev = None
        current = self.head
        # 头结点指向None, 变成尾结点
        # 第二个结点指向头结点, 以此类推
        while current:
            next_node = current.next
            current.next = prev  # None, 旧的第二结点, 旧的第三结点...
            prev = current
            current = next_node
        # 最后遍历的结点(原来的尾结点)设置为头结点
        self.head = prev

    # 把普通列表转成链表
    def init_list(self, data_list):
        """把传入的list转换成链表"""
        # 调用Node, 把传入列表的第1个元素实例化为链表的头结点
        self.head = Node(data_list[0])
        temp = self.head
        # 从第二个元素开始遍历
        for i in data_list[1:]:
            node = Node(i)
            # 当前结点指向下一个结点
            temp.next = node
            # 把下一个结点设置为temp
            temp = temp.next


